package cyc2018.分治;

import java.util.LinkedList;
import java.util.List;

/**
 * 不同的二叉搜索树 II
 */
public class Test95 {

   static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
    // 由题意知需要使用层序遍历的方式
    // BST：根节点左节点小于他，右节点大于他
    // 递归求解，i 左边的都小于他，作为左子树； i 右边的都大于他，作为右子树
    // 在左右子树中又要再次追寻可能的各种组合
    public static List<TreeNode> generateTrees(int n) {
        return generateSubtrees(1, n);
    }

    private static List<TreeNode> generateSubtrees(int s, int e) {
        List<TreeNode> res = new LinkedList<TreeNode>();
        if (s > e) {
            res.add(null);
            return res;
        }
        for (int i = s; i <= e; ++i) {
            List<TreeNode> leftSubtrees = generateSubtrees(s, i - 1);
            List<TreeNode> rightSubtrees = generateSubtrees(i + 1, e);
            for (TreeNode left : leftSubtrees) {
                for (TreeNode right : rightSubtrees) {
                    TreeNode root = new TreeNode(i);
                    root.left = left;
                    root.right = right;
                    res.add(root);
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        List<TreeNode> generateTrees = generateTrees(2);
        generateTrees.forEach((e) -> System.out.print(e.val + " "));
    }
}
